/*
Source : https://leetcode.com/problems/multiply-strings/
Author : nflush@outlook.com
Date   : 2016-07-18
*/

/*
43. Multiply Strings
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 67593
?Total Submissions: 278372
?Difficulty: Medium



Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

?The numbers can be arbitrarily large and are non-negative.
?Converting the input string to integer is NOT allowed.
?You should NOT use internal library such as BigInteger.
*/
class Solution {
private:
    void setNumber(int a[], string &num, int len, int mult){
        int up = 0,j = 0;
        for (int i = len;i--; j++){
            int n = mult * (num[i] - '0') + up;
            up = n/10;
            a[j] = n%10;
        }
        a[j] = up;
    }
    void addNumber(int base[], int add[], int len, int start){
        int up = 0, i = 0;
        for (; i < len; i++){
            int num = base[start + i] + add[i] + up;
            base[start + i] = num % 10;
            up = num / 10;
        }
        while (up){
            int num = base[start + i] + up;
            base[start + i] = num % 10;
            i++;
            up = num / 10;
        }
    }
    int arrayLen(int array[], int maxLen){
        int len;
        for(len = maxLen; len > 0 && array[len-1] == 0; len--);
        return len;
    }
public:
    string multiply(string num1, string num2) {
        int zero = 0;
        int lena = num1.size();
        int lenb = num2.size();
        while (lena > 0 && num1[lena-1] == '0'){lena--; zero++; }
        while (lenb > 0 && num2[lenb-1] == '0'){lenb--; zero++; }
        if (lena == 0 || lenb == 0) return "0";

        string &base = lena > lenb ? num2: num1;
        string &mult = lena > lenb ? num1: num2;
        int bLen = min(lena, lenb);
        int mLen = max(lena, lenb);
        int a[10][bLen + 1] = {0};
        bool b[10] = {false};
        int asn[lena + lenb] = {0};


        for (int i = mLen; i--; ){
            int num = mult[i] - '0';
            if (num != 0){
                if(!b[num]){
                    b[num] = true;
                    setNumber(a[num], base, bLen, num);
                }
                addNumber(asn, a[num], bLen + 1, mLen - i -1);
            }
        }

        bLen = arrayLen(asn, lena + lenb);
        char chAsn[bLen + zero + 1];
        for (int i = 0; i < bLen;i++){
            chAsn[i] = asn[bLen - i - 1] + '0';
        }
        for (int i = bLen; i < bLen + zero;i++){
            chAsn[i] = '0';
        }
        chAsn[bLen + zero] = '\0';
        return string(chAsn);
    }
};
